//
//  SearchSolution.cpp
//  leetcode
//
//  Created by Ellie on 2021/2/7.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include "SearchSolution.hpp"

int SearchSolution::binarySearch(vector<int>& input, int value)
{
    // recursion
    // int size = input.size();
    // return binarySerachRecursion(input, value, 0, size - 1);
    
    int size = input.size();
    int low = 0;
    int high = 0;
    while(low >= high)
    {
        int mid = (high - low) / 2 + low;
        if(input[mid] == value)
            return mid;
        else if(input[mid] < value)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

int SearchSolution::binarySearchRecursion(vector<int>& input, int value, int low, int high)
{
    if(low > high)
        return -1;
    int mid = (high - low) / 2 + low;
    
    if(input[mid] == value)
        return mid;
    else if(input[mid] < value)
        return binarySearchRecursion(input, value, mid + 1, high);
    else
        return binarySearchRecursion(input, value, low, mid - 1);
}

int SearchSolution::binarySearchFirstOfIndex(vector<int>& input, int target)
{
    int size = input.size();
    int low = 0;
    int high = size - 1;
    int mid = 0;
    while(low <= high)
    {
        mid = (high - low) / 2 + low;
        if(input[mid] < target)
            low = mid + 1;
        else if(input[mid] > target)
            high = mid - 1;
        if(input[mid] == target)
        {
            if(mid == 0 || input[mid - 1] != target)
                return mid;
            else
                high = mid - 1;
        }
    }
    return -1;
}

int SearchSolution::binarySearchLastOfIndex(vector<int>& nums, int target)
{
    int size = nums.size();
    int low = 0;
    int high = size - 1;
    int mid = 0;
    while(low <= high)
    {
        mid = (high - low) / 2 + low;
        if(nums[mid] < target)
            low = mid + 1;
        else if(nums[mid] > target)
            high = mid - 1;
        else if(nums[mid] == target)
        {
            if(mid == size - 1 || nums[mid + 1] != target)
                return mid;
            else
                low = mid + 1;
        }
    }
    return -1;
}

int SearchSolution::binarySerachFirstGreaterOrEqualIndex(vector<int>& nums, int target)
{
    int size = nums.size();
    
    int low = 0;
    int high = size - 1;
    int mid = 0;
    
    while(low <= high)
    {
        mid = (high - low) / 2 + low;
        if(nums[mid] >= target)
        {
            if(mid == 0 || nums[mid - 1] < target)
                return mid;
            else
                high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}

int SearchSolution::binarySerachLastLessOrEqualIndex(vector<int>& nums, int target)
{
    int size = nums.size();
    
    int low = 0;
    int high = size - 1;
    int mid = 0;
    while(low <= high)
    {
        mid = (high - low) / 2 + low;
        if(nums[mid] <= target)
        {
            if(mid == size - 1 || nums[mid + 1] > target)
                return mid;
            else
                low = low + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

// 35. 搜索插入位置
// 不断逼近结果
int SearchSolution::leetcode35searchInsert(vector<int>& nums, int target)
{
    int size = nums.size();
    int low = 0;
    int high = size - 1;
    int mid = 0;
    while(low <= high)
    {
        mid = (high - low) / 2 + low;
        if(nums[mid] == target)
            return mid;
        if(nums[mid] < target)
            low = mid + 1;
        else if(nums[mid] > target)
            high = mid - 1;
    }
    return low;
}

// 二分法是向下取整，偏向左边
// 部分有序，也可以使用二分法，逐渐逼近结果
// 元素唯一
int SearchSolution::findMin(vector<int>& nums)
{
    int size = nums.size();
    int low = 0;
    int high = size - 1;
    
    while(low < high)
    {
        int mid = (high - low) / 2 + low;
        // 收缩左边，套住我们的最小值
        if(nums[mid] < nums[high])
        {
            high = mid;
        }
        else
        {
            low = mid + 1;
        }
    }
    return nums[low];
}

// 元素不唯一
// 最小值右侧是比最小值大的元素而且是升序的

// if(nums[mid] < nums[high]) 表示当前mid右侧是升序的，最小值是mid或者mid左侧的元素
// if(nums[mid] > nums[high]  表示当前mid左侧是升序的，最小值在右侧
// if(nums[mid] == nums[high]) 将high--，将mid向左收敛

int SearchSolution::findMin154(vector<int>& nums)
{
    int size = nums.size();
    
    int low = 0;
    int high = size - 1;
    int mid = 0;
    while(low < high)
    {
        mid = (high - low) / 2 + low;
        // 表示右半部分是有序的，需要在mid的左侧找
        if(nums[mid] < nums[high])
        {
            high = mid;
        }
        else if(nums[mid] > nums[high])
        {
            low = mid + 1;
        }
        else
        {
            high --;
        }
    }
    return nums[low];
}

int SearchSolution::search33(vector<int>& nums, int target)
{
    int size = nums.size();
    
    int low = 0;
    int high = size - 1;
    int mid = 0;
    
    while(low <= high)
    {
        mid = (high - low) / 2 + low;
        if(nums[mid] == target)
            return mid;
        if(nums[mid] < nums[high])
        {
            if(nums[mid] < target && nums[high] >= target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        else
        {
            if(nums[mid] > target && nums[low] <= target)
                high = mid - 1;
            else
                low = mid + 1;
        }
    }
    return -1;
}

bool SearchSolution::search81(vector<int>& nums, int target)
{
    return false;
}

// 34. 在排序数组中查找元素的第一个和最后一个位置
vector<int> SearchSolution::searchRange(vector<int>& nums, int target)
{
    // find first equal
    // find last equal
    int first = binarySearchFirstOfIndex(nums, target);
    if(first == -1)
        return vector<int>{-1, -1};
    int second = binarySearchLastOfIndex(nums, target);
    return vector<int>{first, second};
}
